#include "pq.h"

/*
int heapsize;

void swap(int *a, int *b)
{
    *a = *a ^ *b;
    *b = *a ^ *b;
    *a = *a ^ *b;
}

int maximum(int a[], int *max)
{
    if (heapsize < 1)
	return -1;

    if (max)
    {
	*max = a[0];
    }

    return 0;
}

int extract_max(int a[], int *max)
{
    if (heapsize < 1)
	return -1;

    if (max)
    {
	*max = a[0];
    }

    a[0] = a[heapsize - 1];
    heapsize -= 1;
    max_heapify(a, 0);

    return 0;
}

void max_heapify(int a[], int i)
{
#if 0	// recursive call edition
    int largest, r, l;

    l = LEFT(i);
    r = RIGHT(i);
    if (l < heapsize && a[l] > a[i])
    {
	largest = l;
    }
    else
    {
	largest = i;
    }

    if (r < heapsize && a[r] > a[largest])
    {
	largest = r;
    }

    //fprintf(stdout, "i(%d), l(%d), r(%d), largest(%d)\n", i, l, r, largest);
    if (largest != i)
    {
	swap(&a[i], &a[largest]);
	// TODO: loop alternative 
	max_heapify(a, largest);
    }
#else
    int l, r, largest = i;

    do {
	i = largest;
	l = LEFT(i);
	r = RIGHT(i);
	if (l < heapsize && a[l] > a[i])
	{
	    largest = l;
	}
	if (r < heapsize && a[r] > a[largest])
	{
	    largest = r;
	}
	if (largest != i)
	{
	    swap(&a[i], &a[largest]);
	}
    } while (largest != i);

#endif
}

void increase_key(int a[], int i, int k)
{
    if (i >= heapsize || k < a[i])
	return;

    a[i] = k;
    while (PARENT(i) >= 0 && a[i] > a[PARENT(i)])
    {
	swap(&a[i], &a[PARENT(i)]);
	i = PARENT(i);
    }
}

int insert(int a[], int maxLen, int key)
{
    if (heapsize >= maxLen)
	return -1;

    heapsize += 1;
    a[heapsize - 1] = 0x80 << ((sizeof(int) - 1) * 8);
    //fprintf(stdout, "%d\n", a[heapsize - 1]);
    increase_key(a, heapsize - 1, key);
    return 0;
}

int build_max_pq(int a[], int hsize, int maxLen)
{
    int i;

    if (hsize > maxLen)
	return -1;

    heapsize = hsize;
    for (i = heapsize / 2 - 1; i >= 0; i --)
    {
	//fprintf(stdout, "build_max_pq: i = %d\n", i);
	max_heapify(a, i);
	// print_a(a, heapsize);
    }

    return 0;
}

void print_a(int a[], int n)
{
    int i;

    if (a == NULL || n <= 0)
	return;

    fprintf(stdout, "%d elements:\n\t", n);
    for (i = 0; i < n; i++)
    {
	fprintf(stdout, "%d\t", a[i]);
	if (i && ((i+1) % N_PER_LINE) == 0)
	{
	    fprintf(stdout, "\n\t");
	}
    }
    fprintf(stdout, "\n");
}

void heap_sort(int a[])
{
    int hsize = heapsize;
    int i;

    for (i = hsize - 1; i >= 1; i --)
    {
	swap(&a[0], &a[i]);
	heapsize -= 1;
	max_heapify(a, 0);
    }
//    heapsize = hsize;
}

void bubble_sort(int a[], int n)
{
    int i, j;

    for (i = 0; i < n - 1; i++)
	for (j = i + 1; j < n; j++)
	    if (a[j] < a[i])
		swap(&a[i], &a[j]);
}
*/

int iPQErrno;
char sPQErrno[512];

int maximum(PQ * pq, int *max)
{
    if (isempty(pq))
	return -1;

    if (max)
	*max = pq->a[0];

    return 0;
}

int extract_max(PQ *pq, int *max)
{
    /*
    if (isempty(pq))
	return -1;

    if (max)
	*max = pq->a[0];
	*/
    if (maximum(pq, max) < 0)
	return -1;

    pq->a[0] = pq->a[pq->count-1];
    pq->count -= 1;
    max_heapify(pq->a, pq->count, 0);

    return 0;
}

int insert(PQ *pq, int key)
{
    if (isfull(pq))
	return -1;

    pq->count += 1;
    pq->a[pq->count - 1] = 0x80 << ((sizeof(int) - 1) * 8);
    return increase_key(pq, pq->count-1, key);
}


void max_heapify(int a[], int hsize, int i)
{
    int l, r, largest = i;

    l = LEFT(i);
    r = RIGHT(i);
    if (l < hsize && a[l] > a[i])
    {
	largest = l;
    }
    if (r < hsize && a[r] > a[largest])
    {
	largest = r;
    }
    if (largest != i)
    {
	swap(&a[i], &a[largest]);
	max_heapify(a, hsize, largest);
    }
}

int increase_key(PQ *pq, int i, int key)
{
    if (i >= pq->count || key < pq->a[i])
	return -1;

    pq->a[i] = key;
    while (PARENT(i) >= 0 && pq->a[PARENT(i)] < pq->a[i])
    {
	swap(&pq->a[PARENT(i)], &pq->a[i]);
	i = PARENT(i);
    }

    return 0;
}

int init_max_pq(PQ *pq, int size)
{
    pq->a = (int *)malloc(sizeof(int) * size);
    if (pq->a == NULL)
	return -1;
    pq->count = 0;
    pq->size = size;

    return 0;
}

void finalize_max_pq(PQ *pq)
{
    if (pq->a)
	free(pq->a);
}

int isfull(PQ *pq)
{
    return (pq->count == pq->size);
}

int isempty(PQ *pq)
{
    return (pq->count == 0);
}

int pq_del(PQ *pq, int i)
{
    if (pq->count <= 0 || i < 0 || i >= pq->count)
        return -1;

    /* for debug
    if (pq->a[pq->count-1] > pq->a[i])
        fprintf(stdout, "GT: %d > %d\n", pq->a[pq->count-1] , pq->a[i]);
    else if (pq->a[pq->count-1] == pq->a[i])
        fprintf(stdout, "EQ: %d > %d\n", pq->a[pq->count-1] , pq->a[i]);
    else
        fprintf(stdout, "LT: %d > %d\n", pq->a[pq->count-1] , pq->a[i]);
        */

    pq->a[i] = pq->a[pq->count-1];
    pq->count -= 1;

    max_heapify(pq->a, pq->count, i);
    /* TODO: does the following necessary? */
    while (i >= 0 && i < pq->count && pq->a[PARENT(i)] < pq->a[i])
    {
        fprintf(stdout, "raise up happened!\n");
        swap(&pq->a[PARENT(i)] , &pq->a[i]);
        i = PARENT(i);
    }

    return 0;
}

int build_max_pq(PQ *pq, int a[], int n)
{
    int i;

    if (n > pq->size)
        return -1;

    memcpy(pq->a, a, sizeof(int) * n);

    pq->count = 1;
    for (i = 1; i < n; i++)
    {
        if (insert(pq, pq->a[i]) != 0)
            return -1;
    }
    return 0;
}
